package ToYesterday.matixRoute12;

import org.junit.Test;

/*
 * [思路]
 * 一行一行算，一行满了回来算第二行 Error:中间有的格子过不去，必须连续。
 * 回溯法走迷宫
 * [过程]
 * 重点：向右，下，向左，向上，如果没有超过k，当前结点+1。记录是否访问
 *
 * */
public class RobotRange {
    int countN = 0;

    @Test
    public void TestR() {
        System.out.println(CountNum(38, 15, 9));
    }

    public int CountNum(int m, int n, int k) {
        boolean[][] boold = new boolean[m][n];
        searchGe(m, n, k, 0, 0, boold);
        return countN;
    }

    public int searchGe(int m, int n, int k, int i, int j, boolean[][] boolmock) {
        if (i < 0 || j < 0 || i >= m || j >= n || calu(i) > k || calu(j) > k || (calu(i) + calu(j)) > k || boolmock[i][j]) {
            return 0;
        }
        countN++;
        boolmock[i][j] = true;
        int b = searchGe(m,n,k,i,j+1,boolmock) + searchGe(m,n,k,i+1,j,boolmock) +
                 searchGe(m,n,k,i,j-1,boolmock)+ searchGe(m,n,k,i-1,j,boolmock);

        return b;
    }

    int calu(int i) {
        int sum = 0;
        while (i > 0) {
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }
}
